In the fields of data storage and communication, data reliability is critical. Specifically, it is important that data transmitted or stored is substantially free from errors when that data is received or retrieved from storage, respectively. Traditional methods for ensuring data reliability have included appending check bits or parity symbols to data prior to transmission or storage whereby upon receipt of the data, the parity symbols may be used to detect and correct errors in the data. A symbol is generally a unit of data, and typically includes a number of bits. The parity symbols add redundancy to data, which is transmitted via and/or stored on a potentially noisy medium. One broad class of redundant error correction techniques is error correction coding (ECC). One class of commonly used ECC algorithms is the Reed-Solomon (RS) class of algorithms.
Another coding technique called modulation or constrained coding is typically used after data is encoded with ECC. The term “modulation coding” refers generally to encoding a data stream to meet a constraint, one or more properties which may be useful or necessary for reception or retrieval of data through a communication or data storage channel. One particular example of modulation coding is run-length limited (RLL) coding. RLL coding adds redundancy and is most often used to guarantee that timing information is present in the data stream when the data stream is received (in the case of data transmission) or retrieved (in the case of data storage). A data stream in its analog form generally includes a series of pulses, often, electrical voltage pulses. The presence of a pulse at a particular bit time corresponds to the presence of a binary one in the RLL coded data stream. Other, more complex, signaling techniques exist and the claims herein apply to those schemes, too. RLL coding provides timing recoverability by encoding the data stream such that the number of consecutive binary zeros in the data stream is limited to a desired maximum number, or k-constraint. The k-constraint ensures that the space between pulses is not too long, and thereby provides timing recoverability because the space between pulses does not carry any timing information. Many variations of RLL codes exist that provide a wide range of k-constraints. In current approaches, a data stream is ECC coded prior to RLL coding. Several problems have been identified with implementing ECC encoding prior to RLL encoding, and more specifically the combination of ECC and RLL encoding in the same system have been identified as causing problems.
Both RLL codes and ECC have code rates that are less than one. Code rate refers to the quotient of the number of input data bits prior to encoding, and the number of data bits after encoding. Any time the number of output bits is less than the number of input bits, the code rate is less that one, and the code is said to introduce redundancy to the system. The overall code rate is the product of the RLL code rate and the ECC code rate. The redundancy added by the RLL code provides timing recovery information; the redundancy added by the ECC provides the ability to correct errors in the data stream. The code rate is a measure of the redundancy introduced into the data. In general, more timing recovery information and error correction information results in a penalty of decreased code rate. Conversely, as the code rate increases, the robustness of the timing information and the ECC decreases. In other words, for ECC as more parity symbols are added to input data during encoding, higher reliability can be achieved. However, as higher reliability is achieved by adding parity symbols, the code rate goes down. In general, a lower code rate adversely impacts design parameters, including storage density requirements (in the case of data storage) and bandwidth requirements (in the case of data transmission).
One problem that has been recognized with respect to RLL coding is error propagation. Error propagation refers to an effect in which errors introduced to data in a data block may be spread to other parts of the data block after RLL decoding. Error propagation due to RLL decoding can drastically reduce data reliability because data errors grow in size (propagate) through the RLL decoding process (which is generally nonlinear) and thereby may corrupt multiple code symbols. An interesting fact about ECC is that the extra parity and the original data work together to correct errors that occur anywhere in the data stream. A corrupted data symbol is just as detrimental as a corrupted parity symbol. In short, error propagation refers to the fact that more errors are seen on the output of the RLL decoder than on the input.
One approach that has been used to limit the effects of error propagation is referred to as reverse ECC. As discussed earlier, a common approach is introducing the ECC code prior to the RLL code. Reverse ECC involves RLL encoding of input data prior to ECC coding. In other words, input data is RLL encoded and subsequently ECC encoded. Since ECC coding adds extra bits, i.e., the parity symbols, reverse ECC requires another step, whereby ECC parity symbols are separately RLL encoded, because the parity symbols may otherwise violate the specified run-length constraint for binary zeros. Although the Reverse ECC approach may limit error propagation, it requires additional logic to implement the second RLL code. The second RLL code has a lower rate than the primary RLL code and requires packing and unpacking logic in the controller and extra gates for its implementation. Implementation of Reverse ECC typically results in greater die size requirements in integrated circuits. Additionally, for a given degree of data reliability, code rate may be reduced because the second RLL encoding increases the block redundancy beyond the amount required for standard (i.e., not reverse) RLL and ECC implementation.